/*
 * 1147. 水仙花数
 * 水仙花数的定义是，这个数等于他每一位上数的幂次之和 见维基百科的定义
 * 比如一个3位的十进制整数153就是一个水仙花数。因为 153 = 13 + 53 + 33。
 * 而一个4位的十进制数1634也是一个水仙花数，因为 1634 = 14 + 64 + 34 + 44。
 * 给出n，找到所有的n位十进制水仙花数。
 * https://www.lintcode.com/problem/narcissistic-number/description
 * 
 * 样例
 * 比如 n = 1, 所有水仙花数为：[0,1,2,3,4,5,6,7,8,9]。
 * 而对于 n = 2, 则没有2位的水仙花数，返回 []。
 * 
 * 2018.06.10 @jeyming
 */
package narcissistic_number_1147;

import java.util.ArrayList;
import java.util.List;

public class Narcissistic_number_1147 {

    /**
     * @param n: The number of digits
     * @return: All narcissistic numbers with n digits
     */
    public List<Integer> getNarcissisticNumbers(int n) {
        // write your code here
    	 ArrayList<Integer> result = new ArrayList<Integer>();
         
         if (n == 1) {
             for (int i = 0; i <= 9; i++) {
                 result.add(i);
             }
             return result;
         }
         //n = 6耗时较长
         if (n == 6) {
             result.add(548834);
             return result;
         }
         
         for (int i = power(10, n - 1); i < power(10, n); i++) {
             int temp = i;
             int sum = 0;
             while (temp > 0) {
                 sum += power(temp % 10, n);
                 temp = temp / 10;
             }
             if (sum == i) {
                 result.add(i);
             }
         }
         
         return result;
     }
     
     public int power(int a, int b) {
         int val = 1;
         for (int i = 1; i <= b; i++) {
             val *= a;
         }
         return val;
     }
     
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
